/**
 * https://leetcode.cn/submissions/detail/582027140/
 * 721. 账户合并
 * Medium, 黄伟杰 2024.11.21
 * 并查集
 */

class Solution
{
    vector<int> f;
    unordered_set<string> is;
    unordered_map<string, int> father;

public:
    // 并查集的通用代码，find(x)查找父辈
    int find(int x)
    {
        return x == f[x] ? x : find(f[x]);
    }

    // 并查集的通用代码，merge(x, y)合并父辈
    void merge(int x, int y)
    {
        int xFather = find(x);
        int yFather = find(y);

        if (xFather != yFather)
            f[yFather] = xFather;
    }
    vector<vector<string>> accountsMerge(vector<vector<string>> &accounts)
    {
        vector<vector<string>> ans;
        f = vector<int>(accounts.size());
        // 把所有名字当作自己的父亲
        for (int i = 0; i < f.size(); i++)
            f[i] = i;
        // 遍历每一个邮箱,的到每个名字的关系
        for (int i = 0; i < accounts.size(); i++)
        {
            for (int j = 1; j < accounts[i].size(); j++)
            {
                if (!is.count(accounts[i][j])) // 如果没有
                {
                    is.insert(accounts[i][j]);
                    father[accounts[i][j]] = i;
                }
                else
                    merge(father[accounts[i][j]], i); // 合并
            }
        }
        // 遍历accounts每个名字，寻找他们的父亲（人和每个名字对应）
        // 用set避免重复和自动排序
        unordered_map<int, set<string>> mail;
        for (int i = 0; i < accounts.size(); i++)
        {
            int t = find(i); // 找父亲
            int len = accounts[i].size();
            for (int j = 1; j < len; j++)
                mail[t].insert(accounts[i][j]);
        }
        // 遍历mail，转换格式
        for (auto it : mail)
        {
            vector<string> res;
            res.push_back(accounts[it.first][0]);
            for (auto mail : it.second)
                res.push_back(mail);
            ans.push_back(res);
        }
        return ans;
    }
};